package com.hj.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * @author hj
 * @Date 2022/1/5
 * @Description: 快速排序
 */
public class QuickSort {

    Logger logger = LoggerFactory.getLogger(QuickSort.class);

    public static int[] quickSort2(int[] array, int start, int end) {
        int pivot = array[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (array[j] > pivot)) {
                j--;
            }
            while ((i < j) && (array[i] < pivot)) {
                i++;
            }
            if ((array[i] == array[j]) && (i < j)) {
                i++;
            } else {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        if (i - 1 > start) {
            array = quickSort2(array, start, i - 1);
        }
        if (j + 1 < end) {
            array = quickSort2(array, j + 1, end);
        }
        return array;
    }

    public void quickSort(int[] array, int left, int right) {
        if (null == array) {
            return;
        }
        logger.info(String.format("left:%s,right:%s", left, right));
        if (left < right) {
            int i = left;
            int j = right;
            // 选取一端值为基数值
            int temp = array[i];
            while (i < j) {
                // 如果 j 处值大于等于基准值,那么不用交换数据,直接将 j 向前移动.
                // 直到 i 等于 j 或者 j处值比基准值小
                while (i < j && array[j] >= temp) {
                    j--;
                }
                // 如果 i<j,说明j处值比基准值小(根据上面循环判断)
                if (i < j) {
                    // 交换 j 与 i 处的值,并将 i 向后移动
                    array[i++] = array[j];
                }
                // 如果 i 处值小于等于基准值,那么将 i 向后移动就可以了
                while (i < j && array[i] <= temp) {
                    i++;
                }
                // 如果 i<j,说明 i 处值比基准值大(根据上面循环判断
                if (i < j) {
                    // 交换 i 与 j 处的值,并将 i 向前移动
                    array[j--] = array[i];
                }
                // 最后将临时基准值填充到 i 处
                array[i] = temp;
            }
            // 对两段各自再快速排序
            quickSort(array, left, i - 1);
            quickSort(array, j + 1, right);
        }
        System.out.println(Arrays.toString(array));

    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] array = {5, 9, 125, 6, 85, 97, 45, 3, 25, 64, 36, 98, 103, 45, 12, 35};
        // 这儿有讲究 左边取索引0 右边索引取总长度-1
        quickSort.quickSort(array, 0, array.length - 1);
        for (int a : array) {
            System.out.println(a);
        }
        System.out.println("-------------------------------------");
        int[] array2 = {3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};
        // 这儿有讲究 左边取索引0 右边索引取总长度-1
        quickSort2(array2, 0, array2.length - 1);
        for (int a : array2) {
            System.out.println(a);
        }
    }

}
